#ifndef _L_BV_TREE_120118_BV_TREE_H
#define _L_BV_TREE_120118_BV_TREE_H

#include <ltypes.h>
#include <lmacros.h>
#include <ltriMesh.h>

#include "BVTreeIter.h"

#include <boost/assert.hpp>
#include <boost/noncopyable.hpp>

#include <vector>

LLIB_BEGIN
namespace geom {

/* Here we define bounding volume hierarchy data structure. */

/* This BVTree_CBT we built up, is a complete binary tree,
 * which can be saved in array and indexed easily.
 */
template <typename BVNode_t>
class BVTree_CBT : public boost::noncopyable {
public:
    /* The node type definition */
    typedef BVNode_t                            BVNode;
    typedef BVTreeIter< BVTree_CBT<BVNode_t> >  Iter;

    /* Constructor */
    BVTree_CBT() : _mesh(NULL), _nodeNum(0), _nodeList(NULL), _leafNum(0), _leafIndexList(NULL), _firstLeafIndex(-1), _lastLeafIndex(-1) {}
    /* Destructor
       The destructor need to free all tree nodes.
     */
    ~BVTree_CBT();

    /* Initializer : input the corresponding mesh and build up tree */
    void Init(TriMesh& triMesh);

    /* The hierarchy node number query */
    inline Int32 GetNodeNum() const { return _nodeNum; }
    inline Int32 GetLeafNum() const { return _leafNum; }

    /* Get the root node pointer */
    inline BVNode_t* GetRoot() const { return _nodeList; }

    /* Create a BVTree traversal iterator */
    inline Iter* CreateIter(typename Iter::TraversalType type) { return Iter::Create(*this, type); }

private:
    /* The pointer of triangle mesh with tree is built on */
    TriMesh*    _mesh;

    /* The tree nodes array list */
    Int32       _nodeNum;
    BVNode_t*   _nodeList;

    /* The corresponding triangle index of leaf nodes */
    Int32       _leafNum;
    Int32*      _leafIndexList;

    /* The first and last index of leaf within _nodeList */
    Int32       _firstLeafIndex;
    Int32       _lastLeafIndex;

    /* Building hierarchy according to elements' center position */
    void    build(const std::vector<Vec3f>& elementPostions);
    void    leafArrangement(const std::vector<Vec3f>& elementPostions, std::vector<Int32>& leafIndex) const;
    Int32   completeBinaryTreeLeafDivide(Int32 leafNum) const;

    /* The friends */
    friend BVNode_t;
};


} // end of namespace geom
LLIB_END

#include "BVTree.hpp"

#endif
